package com.atguigu.recursion;

import java.util.Arrays;

public class EightQueenDemo {
    public static void main(String[] args) {
        chessBox chessBox = new chessBox();
        chessBox.print();

        chessBox.putQueen(0,0);

        chessBox.setQueenOnBox();
        chessBox.print();
    }
}

class chessBox{
    private int[][] box=new int[8][8];

    // 8个皇后内容.0,1表示行号,列好;2表示是否已落子.0未落子,1已落子.
    private int[][] queenPositions=new int[8][3];
    private int nextQueen=0;

    public chessBox() {
    }

    public void print(){
        System.out.println("chess box:");
        for (int[] ints : box) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
    }

    public void reset(){
        for (int[] ints : box) {
            Arrays.fill(ints, 0);
        }
    }

    public void setQueenOnBox(){
        for (int[] queenPosition : queenPositions) {
            if (queenPosition[2]==1) {
                box[queenPosition[0]][queenPosition[1]]=1;
            }
        }
    }

    public boolean twoQueenMeet(int row1,int col1,int row2,int col2){
        if (row1==row2) {
            return true;
        }
        if (col1==col2) {
            return true;
        }
        if (row1-row2==col1-col2) {
            return true;
        }
        return false;

    }

    public boolean isCurrentPositionOk(int row,int col){
        for (int[] queenPosition : queenPositions) {
            if (queenPosition[2]==1) {
                boolean twoQueenMeet = twoQueenMeet(queenPosition[0], queenPosition[1], row, col);
                if(twoQueenMeet){
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * 可能涉及到两种递归
     * 1. 大局是否成功
     * 成功结束点: 所有皇后位置均合法
     * 失败结束点: 当前放置的皇后位置不合法=>不能找到一个合适的皇后位置合法
     * 中继点: 按照某种策略放置下一个皇后的位置
     *
     */
    public boolean putQueen(int row,int col){
        System.out.println("nextQueen:"+nextQueen+","+row+","+col+":"+ Arrays.deepToString(queenPositions));

        // 成功分支(所有的queen位置均可以)
        if (queenPositions[7][2]==1) {
            System.out.println(Arrays.deepToString(queenPositions));
            return true;
        }

        // 失败终结点
        // 失败终结分支(当前防止的queen位置不合法)
        if (queenPositions[6][2]==1) {
            return isCurrentPositionOk(row,col);
        }

        // 中继点
        // 放置策略1: 无脑遍历放置 (待找到更好的策略)
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                // 假定是ok的
                queenPositions[nextQueen++]=new int[]{i,j,1};
                if(putQueen(i,j)){
                    return true;
                }else{
                    queenPositions[--nextQueen]=new int[]{i,j,0};
                }
            }
        }

        return false;
    }

}
